package com.heihei.demo02;

import java.util.List;

/**
 *  两数相加
 *
 * @version 1.0
 * @since JDK1.8
 * @author duanhengfei
 * @date 2021年03月01日 14:05:51
 */
public class AddTwoNum {
    public static void main(String[] args) {
        //测试
//        ListNode l1Bai = new ListNode(3);
//        ListNode l1Shi = new ListNode(4, l1Bai);
//        ListNode l1Ge = new ListNode(2, l1Shi);
//
//        ListNode l2Bai = new ListNode(4);
//        ListNode l2Shi = new ListNode(6, l2Bai);
//        ListNode l2Ge = new ListNode(5, l2Shi);
//
//        ListNode result = addTwoNumbers(l1Ge, l2Ge);
//        System.out.println(result);


        //测试
//        ListNode l1 = new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9)))))));
//        ListNode l2 = new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9))));
//        ListNode result = addTwoNumbers(l1, l2);
//        System.out.println(result);

        //测试
        ListNode l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
        ListNode l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
        ListNode result = addTwoNumbers02(l1, l2);
        System.out.println(result);

    }

//    /**
//     * 方法描述: 方法一（代码有些冗长）
//     * 用时 2ms， 击败 99.99%
//     * 内存 38.9MB，  击败 34.58%
//     *
//     * @param l1
//     * @param l2
//     * @Return {@link ListNode}
//     * @throws
//     * @author duanhengfei
//     * @date 2021年03月01日 14:27:36
//     */
//    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//        //进位
//        int jinwei = 0;
//        //指针
//        ListNode flag1 = l1;
//        ListNode flag2 = l2;
//        //用来存储结果
//        ListNode result = null;
//        //结果指针
//        ListNode flagResult = null;
//        //开始执行加法
//        while(flag1 != null && flag2 != null) {
//            int currSum = flag1.val + flag2.val + jinwei;
//            if(currSum > 9) {
//                currSum = currSum - 10;
//                jinwei = 1;
//            } else {
//                jinwei = 0;
//            }
//            //建节点
//            ListNode currNode = new ListNode(currSum);
//            if(flagResult == null) {
//                flagResult = currNode;
//                result = currNode;
//            } else {
//                flagResult.next = currNode;
//                flagResult = currNode;
//            }
//            //两个指针移动
//            flag1 = flag1.next;
//            flag2 = flag2.next;
//        }
//        while (flag1 != null) {
//            int currSum = flag1.val + jinwei;
//            if(currSum > 9) {
//                currSum = currSum - 10;
//                jinwei = 1;
//            } else {
//                jinwei = 0;
//            }
//            //建节点
//            ListNode currNode = new ListNode(currSum);
//            if(flagResult == null) {
//                flagResult = currNode;
//                result = currNode;
//            } else {
//                flagResult.next = currNode;
//                flagResult = currNode;
//            }
//            //指针移动
//            flag1 = flag1.next;
//        }
//        while (flag2 != null) {
//            int currSum = flag2.val + jinwei;
//            if(currSum > 9) {
//                currSum = currSum - 10;
//                jinwei = 1;
//            } else {
//                jinwei = 0;
//            }
//            //建节点
//            ListNode currNode = new ListNode(currSum);
//            if(flagResult == null) {
//                flagResult = currNode;
//                result = currNode;
//            } else {
//                flagResult.next = currNode;
//                flagResult = currNode;
//            }
//            //指针移动
//            flag2 = flag2.next;
//        }
//        //看最后一位的进位，如果进位没有归0，则再往前进一位
//        if(jinwei != 0) {
//            ListNode currNode = new ListNode(jinwei);
//            if(flagResult == null) {
//                flagResult = currNode;
//                result = currNode;
//            } else {
//                flagResult.next = currNode;
//                flagResult = currNode;
//            }
//        }
//        return result;
//    }

    /**
     * 方法描述: 代码进行了一定的封装和精简（但是所用内存上升了）
     * 用时 2ms， 击败 99.99%
     * 内存 39MB，  击败 24.89%
     *
     * @param l1
     * @param l2
     * @Return {@link ListNode}
     * @throws
     * @author duanhengfei
     * @date 2021年03月01日 14:27:36
     */
    public static ListNode addTwoNumbers02(ListNode l1, ListNode l2) {
        //进位
        int jinwei = 0;
        //指针
        ListNode flag1 = l1;
        ListNode flag2 = l2;
        //用来存储结果
        ListNode result = new ListNode(0);
        //结果指针
        ListNode flagResult = result;
        //开始执行加法
        while(flag1 != null && flag2 != null) {
            int currSum = flag1.val + flag2.val + jinwei;
            int currNum = currSum % 10;
            jinwei = currSum / 10;
            //建节点
            flagResult = buildNode(currNum, flagResult);
            //两个指针移动
            flag1 = flag1.next;
            flag2 = flag2.next;
        }
        while (flag1 != null) {
            int currSum = flag1.val + jinwei;
            int currNum = currSum % 10;
            jinwei = currSum / 10;
            //建节点
            flagResult = buildNode(currNum, flagResult);
            //指针移动
            flag1 = flag1.next;
        }
        while (flag2 != null) {
            int currSum = flag2.val + jinwei;
            int currNum = currSum % 10;
            jinwei = currSum / 10;
            //建节点
            flagResult = buildNode(currNum, flagResult);
            //指针移动
            flag2 = flag2.next;
        }
        //看最后一位的进位，如果进位没有归0，则再往前进一位
        if(jinwei != 0) {
            flagResult = buildNode(jinwei, flagResult);
        }
        return result.next;
    }

    private static ListNode buildNode(int currNum, ListNode flagResult) {
        ListNode currNode = new ListNode(currNum);
        flagResult.next = currNode;
        return currNode;
    }
}

/*
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。





*/